import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int first = 0, n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        while(first < n - 3){
            // 确定了第一个数，就剩余的三个数字的和是 target - nums[first]
            int second = first + 1;
            while(second < n - 2){
                int left = second + 1,right = n -1;
                while(left < right){
                    long sum = (long) nums[first] + nums[second] + nums[left] + nums[right];
                    if(sum < target ){
                        left++;
                    }else if(sum > target ){
                        right--;
                    }else{
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[first]);list.add(nums[second]);list.add(nums[left]);list.add(nums[right]);
                        ret.add(list);
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                second++;
                while(second < n && nums[second] == nums[second - 1]) second++;
            }
            first++;
            while(first < n && nums[first] == nums[first - 1]) first++;
        }
        return ret;
    }
}
